package org.example.myleet.p437;

import org.example.myleet.Utils.TreeNode;

/**
 * 最容易想到的方式，双重DFS，第一重DFS用于遍历节点，第二重DFS用于针对某个节点进行所有子路径的搜索
 * O(n^2)复杂度
 * 存在大量重复计算，并非最优
 */
public class Solution1 {

    private int count;

    private int targetSum;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        count = 0;
        this.targetSum = targetSum;
        dfs(root);
        return count;
    }

    private void dfs(TreeNode node) {
        searchNode(node, 0);
        if (node.left != null) {
            dfs(node.left);
        }
        if (node.right != null) {
            dfs(node.right);
        }
    }

    private void searchNode(TreeNode node, int pathSum) {
        int sum = pathSum + node.val;
        if (sum == targetSum) {
            ++count;
        }
        if (node.left != null) {
            searchNode(node.left, sum);
        }
        if (node.right != null) {
            searchNode(node.right, sum);
        }
    }
}
